package com.renyq.algorithm.graph.applicate

import com.renyq.algorithm.graph.structure.Node
import java.util.*

object GraphBfs {
    /**
     * 广度优先遍历图
     *
     * @param node 头
     */
    @JvmStatic
    fun bfs(node: Node?) {
        if (node == null) {
            return
        }
        val queue: Queue<Node> = LinkedList()
        //因为可能有环，所以需要一个HashSet来保存遍历过的节点
        val set = HashSet<Node>()
        queue.add(node)
        set.add(node)
        while (!queue.isEmpty()) {
            val curr = queue.poll()
            //System.out.println(curr.value);
            for (edge in curr.edges) {
                val toNode = edge.to
                val weight = edge.weight
                println("${curr.value}->${toNode.value}($weight)")
            }
            for (next in curr.nexts) {
                if (!set.contains(next)) {
                    set.add(next)
                    queue.add(next)
                }
            }
        }
    }
}